To facilitate air traffic control operations, an airspace may be divided into a number of adjacent three-dimensional volumes comprising the space. The trajectory or path of an airborne vehicle (e.g., an airplane, helicopter, airship, balloon, missile, rocket, or the like) through a three-dimensional airspace may be divided into a number of consecutive segments represented by four-dimensional information (e.g., latitude, longitude, altitude and time) defining various points along the path. The intersections of the segments comprising the airborne vehicle's path with the boundaries of each volume are needed in order to determine when the airborne vehicle will enter particular volumes. By finding the latitude, longitude, and altitude of the intersection points, the time that the airborne vehicle enters each volume can be found (assuming information regarding the airborne vehicle's air speed is also available). The times that the airborne vehicle enters particular volumes comprising the airspace are relevant, for example, to controlling when information about the airborne vehicle is provided to air traffic controllers responsible for controlling particular volumes of the airspace.
Some techniques for determining the relevant intersections involve comparing each segment of the path with all of the volumes of the partitioned three-dimensional space. As may be appreciated, determining the intersection points in this manner can be a computation intensive process, particularly when multiple paths through the partitioned airspace are being simultaneously considered. For example, where the path includes N segments and the airspace includes M volumes, the compute time is on the order of N×M. Furthermore, even if a particular segment is found to intersect the boundary of a particular volume, the comparisons for such segment are not complete as it may intersect additional volume boundaries.